package com.zhj.structure.linear.utils;

import java.util.Arrays;

/**
 * @PackageName:com.zhj.structure.utils
 * @ClassName:MyArray
 * @auter: 朱慧杰
 * @date:2020/8/8 0008 10:03
 **/
public class MyArray {

    private int[] elements;

    public MyArray() {
        elements = new int[0];
    }

    public int size() {
        return elements.length;
    }

    public void show() {
        System.out.println(Arrays.toString(elements));
    }

    public void add(int num) {
        int[] newArr = new int[elements.length+1];
        for (int i = 0; i < elements.length; i++) {
            newArr[i] = elements[i];
        }
        newArr[elements.length] = num;
        elements = newArr;
    }

    public void delete(int index) {
        check(index);

        int[] newArr = new int[elements.length-1];
        for (int i = 0; i < elements.length-1; i++) {
            if(i<index) {
                newArr[i] = elements[i];
            } else {
                newArr[i] = elements[i+1];
            }
        }
        elements = newArr;
    }

    public int get(int index) {
        return elements[index];
    }

    public void insert(int index, int num) {
        check(index);

        int[] newArr = new int[elements.length+1];
        for (int i = 0; i < elements.length; i++) {
            if (i<index) {
                newArr[i] = elements[i];
            } else {
                newArr[i+1] = elements[i];
            }
        }
        newArr[index] = num;
        elements = newArr;
    }

    public void set(int index, int num) {
        check(index);

        elements[index] = num;
    }

    public void check(int index) {
        if(index<0 || index>elements.length-1) {
            throw new RuntimeException("数组下标越界！！！");
        }
    }

    // 线性查找
    public int search(int target) {
        // 目标元素所在下标
        int index = -1;

        for (int i = 0; i < elements.length; i++) {
            if (elements[i]==target) {
                index = i;
                break;
            }
        }
        return index;
    }

    // 二分查找
    public int binarySearch(int target) {

        int index = -1;
        // 开始位置
        int begin = 0;
        // 结束位置
        int end = elements.length-1;
        // 中间位置
        int mid = (begin+end) / 2;

        while (true) {
            if(begin >= end){
                break;
            }
            if (elements[mid] == target) {
                index = mid;
                break;
            } else {
                if (elements[mid] > target) {
                    end = mid - 1;
                } else {
                    begin = mid + 1;
                }
                mid = (begin+end) / 2;
            }
        }

        return index;
    }

    public void sort() {
        Arrays.sort(elements);
    }

}
